
class Vertex:
    """顶点Vertex类 邻接列表"""
    def __init__(self,key):
        """构造顶点"""
        self.id=key     #顶点信息
        self.connectedTo={}     #邻接列表，保存与顶点链接的边信息
    def addNeighbor(self,nbr,weigth=0):
        """添加连接的边和权重"""
        self.connectedTo[nbr]=weigth
    def __str__(self):
        """打印"""
        return str(self.id)+'connectedTo'\
            +str([x.id for x in self.connectedTo])
    def getConnectedtions(self):
        """获取所有的连接边"""
        re=self.connectedTo.keys()
        return re
    def getId(self):
        """获取顶点ID"""
        re=self.id
        return re
    def getWeigth(self,nbr):
        """获取顶点和相连的某条边的权重"""
        re=self.connectedTo[nbr]

class Graph:
    """图 Graph类 保存了包含所有顶点的主表"""
    def __init__(self):
        self.vertlist ={}
        self.numVertices = 0

    def addVertex(self,key):
        """添加新的顶点"""
        self.numVertices=self.numVertices + 1
        newVertex=Vertex(key)   #key实例化为顶点
        self.vertlist[key]=newVertex    #添加到邻接表里
        return newVertex
    def  getVertex(self,n):
        """通过key查找顶点从图中获取n这个顶点，存在就打印"""
        if n in self.vertlist:
            return self.vertlist[n]
        else:
            return None
    def __contains__(self, item):
        """特殊方法，in再这里面"""
        return item in self.vertlist
    def addEdge(self,beg,end,weigth):
        """添加一条边"""
        if beg not in self.vertlist:    #没有顶点就先添加
            self.addVertex(beg)
        if end not in self.vertlist:
            self.addVertex(end)
        #添加完点，再添加边
        #调用起始顶点的方法来添加邻接边
        self.vertlist[beg].addNeighbor(self.vertlist[end],weigth)
    def getVertices(self):
        """获取所有顶点,以列表返回"""
        return self.vertlist.keys()
    def __iter__(self):
        """允许该类进行迭代"""
        rs=iter(self.vertlist.values())
        return rs


# 测试
if __name__=="__main__":
    g=Graph()
    for i in range(6):
        # 添加顶点
        g.addVertex(i)
    g.vertlist
    g.addEdge(0,1,5)
    g.addEdge(0,5,2)
    g.addEdge(2,3,9)
    g.addEdge(3,4,7)
    g.addEdge(3,5,3)
    g.addEdge(4,0,1)
    g.addEdge(5,4,8)
    g.addEdge(5, 2, 1)
    # 遍历顶点
    for v in g:
        # 获取所有的边的信息
        for w in v.getConnectedtions():
            print("(%s,%s)"%(v.getId(),w.getId()))












